Radio Frequency Identification (RFID) systems, which are expected to be technically promising systems in the future ubiquitous computing era, are systems for automatically identifying objects by reading information from tags, attached to the objects, through readers. The most important functional issue for RFID readers is that the RFID readers can rapidly identify all tags.
However, when two or more tags send signals over a single radio channel at the same time, the radio signals collide, and the occurrence of such a collision may result in cases where it obstructs the rapid identification of tags or prevents the readers from identifying tags. Accordingly, new RFID tag identification techniques capable of reducing the frequency of the occurrence of collisions and rapidly identifying tags even though collisions occur in an RFID system, including a plurality of readers and low functionality tags, are required.
Tag identification protocols may be classified into Aloha-based protocols and tree-based protocols. The Aloha-based tag identification protocols employ a method in which tags select a random time and send the Identifications (IDs) thereof to a reader. Various variants thereof include Pure Aloha, Slotted Aloha, and Frame Slotted Aloha.
The Aloha-based protocols can reduce the frequency of the occurrence of collisions from the point of view of probability, but cannot completely prevent the occurrence of collisions. In particular, in the Aloha-based protocols, a tag starvation problem, in which a specific tag is not identified by a reader for a long time due to a collision, may arise. Such a tag starvation phenomenon is a very great disadvantage to applications that attach great importance to accuracy, such as logistic management. Accordingly, the Aloha-based protocols are a representative example of probabilistic anti-collision protocols because the Aloha-based protocols cannot guarantee the identification of all tags.
In contrast, the tree-based tag identification protocols are tag identification techniques for tracking the occurrence of collisions and detecting the existence of tags. A representative of the tree-based tag identification protocol is a binary tree protocol that is used in ISO/IEC 18′-6, type B. The binary tree protocols employ a method of dividing tags into two groups at the time of a collision using, a tag counter and a random number generator and extending the search space. Meanwhile, in the query tree protocols, a query, including a several-bit prefix, is sent, and only a tag possessing an ID coinciding with the prefix responds, using its own ID.
The query tree protocols have an advantage in that the function of the tags is simple compared to that of the binary tree protocols because the tags determine only whether IDs coincide with prefixes, but have a problem in that a significant identification delay may occur according to the type of distribution of the tag IDs. The tree-based tag identification protocols do not cause tag starvation, but cause a significant identification delay.
Accordingly, a tag identification technique for enabling a reader to rapidly identify all tags without tag starvation is required.